home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d18 / futils.arc / FSTACK.DOC < prev    next >
Encoding:
Text File  |  1991-04-28  |  7.0 KB  |  216 lines
  1.  
  2. ********************************************************************
  3. ************************ FSTACK by Rex Kerr ************************
  4. ************************ Copyright (C) 1989 ************************
  5. ********************************************************************
  6.  
  7. This is a Turbo Pascal unit written in assembly language that lets
  8. you create stacks that can be used like the CPU's main stack.  You
  9. can have either byte or word stacks, and you can switch as often as
  10. you like.  You can only have one active byte or word stack at one
  11. time, though.
  12.  
  13. There are 7 routines for word stacks, and seven more for byte stacks.
  14.  
  15. ***
  16.  
  17. InitWStack(var buf; len : word);
  18.  
  19. This initializes the word stack.  Len is the length of buf.  If you
  20. are passing a pointer to something, make sure you pass the something
  21. instead of the pointer:
  22.  
  23. var st : ^string;
  24. begin
  25.      new(st);
  26.      initwstack(st^,sizeof(st^));  { Right. }
  27.      initwstack(st,sizeof(st));    { Now your buffer is the pointer!
  28.                                      You only have 4 bytes! }
  29.      initwstack(st,sizeof(st^));   { This is dangerous!  If you do
  30.                                      too much pushing, you'll run
  31.                                      past the 4 byte pointer ... }
  32.      initwstack(st^,sizeof(st));   { This is wasteful!  You have 256
  33.                                      bytes available, but have said
  34.                                      you only have 4 }
  35.      dispose(st);
  36. end.
  37.  
  38. ***
  39.  
  40. InitBStack(var buf; len : word);
  41.  
  42. This is exactly the same as InitWStack, except it initializes the
  43. byte stack.
  44.  
  45. ***
  46.  
  47. ClearWStack;
  48.  
  49. This just clears the word stack.
  50.  
  51. ***
  52.  
  53. ClearBStack;
  54.  
  55. This clears the byte stack.
  56.  
  57. ***
  58.  
  59. WStackEmpty : boolean;
  60.  
  61. This returns true if the word stack is empty.
  62.  
  63. ***
  64.  
  65. BStackEmpty : boolean;
  66.  
  67. This returns true if the byte stack is empty.
  68.  
  69. ***
  70.  
  71. PushW(w : word);
  72.  
  73. This pushes one word onto the word stack (if it isn't full).
  74.  
  75. ***
  76.  
  77. PushB(b : byte);
  78.  
  79. This pushes one byte onto the byte stack (if it isn't full).
  80.  
  81. ***
  82.  
  83. PopW : word;
  84.  
  85. This pops one word from the word stack.  It is a function for
  86. flexibility and speed.
  87.  
  88. ***
  89.  
  90. PopB : byte;
  91.  
  92. This pops one byte from the byte stack.
  93.  
  94. ***
  95.  
  96. WStackSize : word;
  97.  
  98. This returns the current number of entries in the word stack.  To
  99. find the maximum word size do:
  100.  
  101.      Max_Size := sizeof(buf) shr 1;
  102.  
  103. And to find the number of free spaces (assuming you have found
  104. Max_Size) you do:
  105.  
  106.      free_spaces := Max_Size - WStackSize;
  107.  
  108. ***
  109.  
  110. BStackSize : word;
  111.  
  112. BStackSize returns the number of entries in the byte stack.
  113. Max_Size for the byte stack is the same thing as sizeof(buf).
  114.  
  115. ***
  116.  
  117. SetWStack(size : word);
  118.  
  119. You use this for swapping stacks.  Like this:
  120.  
  121. var bufa,bufb : array[1..100] of byte;
  122.     sizea : word
  123. begin
  124.      initwstack(bufa,sizeof(bufa)); { Initialize the stack         }
  125.      ( . . . )                      { Do some stuff to it          }
  126.      sizea := wstacksize;           { Get the size of the stack    }
  127.      initwstack(bufb,sizeof(bufb)); { Re-initialize stack #2       }
  128.      ( . . . )                      { Do whatever with stack #2    }
  129.      initwstack(bufa,sizeof(bufa)); { Back to stack #1, but it
  130.                                       thinks it is empty }
  131.      setwstack(sizea);              { Now we're back to the first
  132.                                       stack the way it was }
  133. end.
  134.  
  135. Please note that only pushes actually change the values in the
  136. stack.  The others just set different hidden variables or read
  137. from the stack.  SetWStack just sets the length of the stack to
  138. what size you specify; it in no way changes the contents of the
  139. stack.  ClearWStack just calls SetWStack(0).
  140.  
  141. ***
  142.  
  143. SetBStack(size : word);
  144.  
  145. This does for the byte stack what SetWStack does for the word stack.
  146.  
  147. ***
  148.  
  149. One useful place for this is in a non-recursive form of QuickSort.
  150.  
  151. For short stacks, FSTACK is much better than a linked list stack.
  152. Here are the reasons why:
  153.  
  154. 1) It is much faster (3 or 4 times, I think)
  155. 2) It has no overhead per item
  156. 3) You can access the stack as an array
  157.  
  158. You also can have just the amount of space you want like this:
  159.  
  160. program Get_Just_Enough;
  161. uses fstack;
  162. type stackarry : array[1..100] of byte;
  163. var b : ^stackarry;
  164.     len : word;
  165. begin
  166.      len := 14;                 { Or however much you need }
  167.      getmem(b,len);             { Get the memory           }
  168.      initstack(b^,sizeof(b^));  { Initialize the stack     }
  169.      ( . . . )                  { Use the stack            }
  170.      freemem(b,len);            { Free the memory used     }
  171. end.
  172.  
  173. It isn't a good idea to reallocate b while you are using the stack,
  174. in case the place where b is stored is moved.  If it is moved,
  175. you can fix that with the Qmove procedure in FMISC.  The regular
  176. move also works, but Qmove is twice as fast.  Like this:
  177.  
  178. uses fmisc,fstack;
  179. type stackarry := array[1..100] of word;
  180. { If range checking is off, the 1..100 may be any size.  If it's on,
  181.   stackarry must be at least as large as the largest getmem (to avoid a
  182.   range check error) }
  183. var len,size : word;             { len is to store the getmem value,
  184.                                    size is to store wstacksize }
  185.     b,temptr : ^stackarry;       { You'll need the extra pointer }
  186. begin
  187.      len := 14;           { Set getmem length                     }
  188.      getmem(b,len);       { Get the memory                        }
  189.      initwstack(b^,len);  { Initialize the stack                  }
  190.      ( . . . )            { Use the stack & find it is too small  }
  191.      temptr := b;         { Save the address of the buffer        }
  192.      freemem(b,len);      { Free the buffer's memory              }
  193.      len := 28;           { Set the new length                    }
  194.      getmem(b,len);       { Get the memory                        }
  195.      size := wstacksize;  { Get the stack size                    }
  196.      if temptr <> b then  { If temptr <> b, the b has been moved  }
  197.      begin
  198.           qmove(temptr,b,size);   { Move the stack values to the
  199.      end;                           new location }
  200.      initwstack(b^,len);  { Re-initialize the stack to the new
  201.                             maximum length (and maybe location)   }
  202.      setwstack(size);     { Set the stack to use the old pushed
  203.                             values                                }
  204.      ( . . . )            { Do whatever you want                  }
  205.      freemem(b,len);      { Free the allocated memory             }
  206. end.                      { We're done.                           }
  207.  
  208. All of the byte stack things work just like the word stack things,
  209. except you push and pop bytes.  You will probably have to use
  210. value typecasting (for things like characters and integers).
  211. And also you'll have to split things like longints up.  When you
  212. are doing that, remember that if you push the high part first and
  213. then the low part, you should pop the low part and then the high
  214. part to get it back the same way.
  215.  
  216.